Networks enable computers to quickly send e-mail, video, audio, and other electronic information to other computers very far away. Typically, the information is transmitted in packets. A packet is like an envelope with a return address (the packet source) and a mailing address (the packet destination). Much as an envelope reaches its mailing address via a series of post offices, a packet reaches its destination by winding its way through different computers in the network. One type of network computer is known as a router. When a router receives a network packet, the router typically tries to figure out how to forward the packet to its destination in the least amount of time.
Instead of addressing packets to a single destination, a packet may be addressed to a group. The packet is sent to each member of the group even though the different members may be very far apart from one another. This is known as xe2x80x9cmulticasting.xe2x80x9d A number of different approaches to multicasting are known. Some of these approaches have been embodied in multicasting protocols such as MOSPF (Multicast Open Short Path First), DVMRP (Distance Vector Multicast Router Protocol), and PIM-DM (Protocol Independent Multicasting Dense Mode). A router executing one of these protocols agrees to interact with other routers and forward packets in the manner described by the protocol.
In general, in one aspect, the invention features a method of processing a multicast packet being sent from a multicast source address to members of a multicast group. The method includes determining whether a first forwarding cache that stores forwarding information for ranges of addresses includes a first forwarding cache entry for a range of addresses that includes the source address. If the first forwarding cache includes the first forwarding cache entry, adding an entry to a second forwarding cache for the specific source address and group of the packet using the forwarding information associated with the first forwarding cache entry.
Embodiments may include one or more of the following features. The method may further include adding an entry in the first forwarding cache for a range of addresses that includes the source address of the packet. Adding such an entry may include using a multicast protocol routing algorithm, such as MOSPF, DVMRP, or PIM-DM, to determine forwarding information for the range of address. Adding the entry may include determining a range of source addresses in table of multicast source addresses that include the source address of the packet. The range of source addresses may be a most specific range of source addresses including the source address of the packet. The forwarding information may include identification of one or more incoming interfaces and one or more outgoing interfaces.
The method of claim 1 may further include determining whether a second forwarding cache entry exists for the source address and group of the packet in the second forwarding cache. If the second forwarding entry exists, the method may include forwarding the packet in accordance with the forwarding information of the second forwarding entry. The address ranges may be nested address ranges.
In general, in another aspect, a method of updating a first entry in a first forwarding cache that stores forwarding information for multicast source address, multicast group pairs, can include selecting a first entry in a second forwarding cache that stores forwarding information for ranges of multicast source addresses, the range of addresses of the selected second entry including the multicast source address, and replacing the forwarding information for the first entry in the first forwarding cache with forwarding information associated with the selected second entry in the second forwarding cache.
In general, in another aspect, the invention features a memory storing one or more data structures for use in routing multicast network packets from a source to a multicast group. The memory includes a forwarding cache that stores forwarding information for particular source/group pair and a protocol forwarding cache that stores forwarding information for nested ranges of source addresses.
In general, in another aspect, the invention features a computer program product, disposed on a computer readable medium, for processing a multicast packet being sent from a multicast source address to members of a multicast group. The program includes instructions for causing a processor to determine whether a first forwarding cache that stores forwarding information for ranges of addresses includes a first forwarding cache entry for a range of addresses that includes the source address. If the first forwarding cache includes the first forwarding cache entry, the method can add an entry to a second forwarding cache for the specific source address and group of the packet using the forwarding information associated with the first forwarding cache entry.
In general, in another aspect, the invention features A computer program product, disposed on a computer readable medium, for updating a first entry in a first forwarding cache that stores forwarding information for multicast source address, multicast group pairs. The program includes instructions for causing a processor to select a first entry in a second forwarding cache that stores forwarding information for ranges of multicast source addresses, the range of addresses of the selected second entry including the multicast source address. The program also includes instructions that replace the forwarding information for the first entry in the first forwarding cache with forwarding information associated with the selected second entry in the second forwarding cache.
Advantages of the invention will become apparent in view of the following description, including the figures, and the claims.